from typing import List

# time out


class Solution:
    def permute(self, n: int, k: int) -> List[int]:
        self.count = 0
        self.result = []
        used = [False] * n
        
        def backtrack(path: List[int], last_parity: int) -> bool:
            if len(path) == n:
                self.count += 1
                if self.count == k:
                    self.result = path.copy()
                    return True
                return False
            
            if not path:
                candidates = [i + 1 for i in range(n) if not used[i]]
            else:
                required_parity = 1 - last_parity
                candidates = [i + 1 for i in range(n) if not used[i] and (i + 1) % 2 == required_parity]
            
            for num in sorted(candidates):
                idx = num - 1
                used[idx] = True
                if backtrack(path + [num], num % 2):
                    return True
                used[idx] = False
            return False
        
        if backtrack([], None):
            return self.result
        else:
            return []